package backtrack;
import java.util.*;
public class _06_131_分割回文串 {
	List<List<String>> result = new ArrayList<>();
	List<String> item = new ArrayList<>();
	StringBuilder temp;
	String action;
    public List<List<String>> partition(String s) {

    	backtracking(s,0);

    	for (List<String> i: result) {
			for (String j : i) {
				System.out.print(j + " ");
			}
			System.out.println();
		}
    	
    	return result;
    }
    
    public void backtracking(String s, int index) {
    	if(index >= s.length()) {
    		result.add(new ArrayList<>(item));
    		return;
    	}
    	
    	for(int i = index; i < s.length(); i++) {
    		// 获取当前分割的字符串
    		action = s.substring(index,i + 1);
    		// 反转字符串 如果相同说明是回文 不是回文则跳过
    		temp = new StringBuilder(action);
    		if(temp.reverse().toString().equals(action)) {
    			item.add(action);
    		} else {
    			continue;
    		}
    		backtracking(s, i + 1);
    		item.remove(item.size() - 1);
    	}
    }
    
    public static void main(String[] args) {
		new _06_131_分割回文串().partition("abba");
	}
}
